package first.codeTop.huawei;

import java.util.Stack;

/**
 * @ClassName Leetcode739
 * @description:
 * @author: 荣燊
 * @create: 2021-08-04 19:16
 **/
public class Leetcode739 {
    // 每日温度
    public static void main(String[] args) {
        int[] temperatures = {73,74,75,71,69,72,76,73};
        int[] ints = dailyTemperatures(temperatures);
        for (int i : ints) {
            System.out.println(i);
        }
    }

    // 解法：1442ms
    public static int[] dailyTemperatures(int[] temperatures) {
        int[] ints = new int[temperatures.length];
        for (int i=0; i<ints.length; i++) {
            int flag = 0;
            int j = i + 1;
            while (j < temperatures.length) {
                if (temperatures[j] > temperatures[i]) {
                    ints[i] = j - i;
                    break;
                } else {
                    j++;
                }
            }
        }
        return ints;
    }

    // 解法：单调栈
    public static int[] dailyTemperatures1(int[] temperatures) {
        int[] ints = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i=0; i<temperatures.length; i++) {
            int tmp = temperatures[i];
            // 当前元素大于栈顶元素，就一直弹出栈顶元素进行运算
            while (!stack.isEmpty() && tmp > temperatures[stack.peek()]) {
                ints[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return ints;
    }
}
